﻿#define _CRT_SECURE_NO_WARNINGS 1
#include <algorithm>
#include <iostream>
using namespace std;
#include <vector>

//class Solution {
//public:
//    vector<vector<int>> threeSum(vector<int>& nums)
//    {
//        sort(nums.begin(), nums.end());
//        vector<vector<int>> ret;
//        for (int i = 0; i < nums.size() - 2; i++)
//        {
//            int left = i + 1, right = nums.size() - 1;
//            while (left < right)
//            {
//                int sum = nums[left] + nums[right];
//                if (sum > -nums[i])
//                {
//                    right--;
//                }
//                else if (sum < -nums[i])
//                {
//                    left++;
//                }
//                else
//                {
//                    ret.push_back({ nums[i],nums[left],nums[right] });
//                    int t = left;
//                    while (left < right && nums[t] == nums[left])
//                    {
//                        left++;
//                    }
//                    t = right;
//                    while (left < right && nums[t] == nums[right])
//                    {
//                        right--;
//                    }
//                }
//            }
//            while (i < nums.size() - 2 && nums[i] == nums[i + 1])
//            {
//                i++;
//            }
//        }
//        return ret;
//    }
//};

//class Solution {
//public:
//    vector<vector<int>> fourSum(vector<int>& nums, int target)
//    {
//        int n = nums.size();
//        vector<vector<int>> ret;
//        sort(nums.begin(), nums.end());
//        for (int i = 0; i < n; )
//        {
//            //int t1 = target-nums[i];
//
//            for (int j = i + 1; j < n; )
//            {
//                int left = j + 1, right = n - 1;
//                int t2 = target - nums[i] - nums[j];
//                while (left < right)
//                {
//                    int sum = nums[left] + nums[right];
//                    if (sum > t2)
//                    {
//                        right--;
//                    }
//                    else if (sum < t2)
//                    {
//                        left++;
//                    }
//                    else
//                    {
//                        ret.push_back({ nums[i],nums[j],nums[left],nums[right] });
//                        left++, right--;
//
//                        while (left < right && nums[left] == nums[left - 1]) left++;
//                        while (left < right && nums[right] == nums[right + 1]) right--;
//                    }
//                }
//
//                j++;
//                while (j < n && nums[j] == nums[j - 1])j++;
//            }
//            i++;
//            while (i < n && nums[i] == nums[i - 1])i++;
//        }
//        return ret;
//    }
//};
//int main()
//{
//    vector<int> num = { 1,0,-1,0,-2,2 };
//    int t = 0;
//    Solution().fourSum(num,t);
//    return 0;
//}

//class Solution {
//public:
//    int minSubArrayLen(int target, vector<int>& nums)
//    {
//        int left = 0, right = 0;
//        int n = nums.size();
//        int sum = nums[0];
//        int len = 1;
//        int ret = INT_MAX;
//        while (left <= right && right < n)
//        {
//            if (sum < target)
//            {
//                right++;
//                if(right<n)
//                    sum += nums[right];
//                len++;
//            }
//            else
//            {
//                if (len < ret)
//                    ret = len;
//                sum -= nums[left];
//                left++;
//                len--;
//            }
//        }
//        return ret;
//    }
//};
//
//int main()
//{
//    //int target = 7;
//    //vector<int> nums = { 2,3,1,2,4,3 };
//    printf("🖕");
//    //Solution().minSubArrayLen(target, nums);
//    return 0;
//}

//class Solution {
//public:
//    vector<int> singleNumber(vector<int>& nums)
//    {
//        int sum = 0;
//        for (auto i : nums)
//        {
//            sum ^= i;
//        }
//
//        int bit = sum & -sum; //求最小位的1留下
//        int x = 0, y = 0;
//        for (auto i : nums)
//        {
//            if (nums[i] & bit)
//                x ^= nums[i];
//            else
//                y ^= nums[i];
//        }
//
//        return { x,y };
//    }
//};

//class Solution {
//public:
//    int minOperations(vector<int>& nums, int x)
//    {
//        int k = -x;
//        for (auto e : nums)
//        {
//            k += e;
//        }
//        if (k < 0) return -1;
//        int sum = 0;
//        int len = 0;
//        for (int left = 0, right = 0; right < nums.size(); right++)
//        {
//            sum += nums[right];
//            while (sum > k)
//            {
//                sum -= nums[left];
//                left++;
//            }
//            if (sum == k)
//                len = max(len, right - left + 1);
//        }
//        return (len == 0 ? -1 : nums.size() - len);
//    }
//};
//int main()
//{
//    vector<int> nums = { 8828,9581,49,9818,9974,9869,9991,10000,10000,10000,9999,9993,9904,8819,1231,6309 };
//    int x = 134365;
//    Solution().minOperations(nums, x);
//    return 0;
//}

//class Solution {
//public:
//    vector<int> findAnagrams(string s, string p)
//    {
//        int len = p.size();
//
//        char hash_s[26] = { 0 };
//        char hash_p[26] = { 0 };
//        for (auto e : p)
//        {
//            hash_p[e - 'a']++;
//        }
//
//        vector<int> ret;
//        for (int left = 0, right = 0; right < s.size(); right++)
//        {
//            hash_s[s[right] - 'a']++;
//            if (right - left + 1 > len)
//            {
//                hash_s[s[left] - 'a']--;
//                left++;
//            }
//
//            if (right - left + 1 == len && check(hash_s, hash_p))
//                ret.push_back(left);
//        }
//        return ret;
//    }
//
//    bool check(char* hash_s, char* hash_p)
//    {
//        for (int i = 0; i < 26; i++)
//        {
//            if (hash_s[i] != hash_p[i])
//                return false;
//        }
//        return true;
//    }
//};
//
//int main()
//{
//    string s("cbaebabacd");
//    string p("abc");
//    Solution().findAnagrams(s, p);
//    return 0;
//}

#include <unordered_map>
class Solution {
public:
    vector<int> findSubstring(string s, vector<string>& words)
    {
        unordered_map<string, int> hash1;
        for (auto& s : words)
        {
            hash1[s]++;
        }

        vector<int> ret;
        int len = words[0].size(), m = words.size();
        for (int begin = 0; begin < len; begin++)
        {
            unordered_map<string, int> hash2;
            int count = 0;
            for (int left = begin, right = begin; right + len <= s.size(); right += len)
            {
                if (left == 6)
                {
                    printf("断点");
                }
                string in = s.substr(right, len);
                hash2[in]++;
                if (hash2[in] <= hash1[in])
                {
                    count++;//进窗口
                }
                if (right - left + 1 > len * m)//出窗口
                {
                    string out = s.substr(left, len);
                    if (hash2[out] <= hash1[out])
                    {
                        count--;
                    }
                    hash2[out]--;
                    left += len;
                }
                if (count == m)
                    ret.push_back(left);
            }
        }
        return ret;
    }
};

int main()
{
    string s = "barfoothefoobarman";
    vector<string> words = { "foo","bar" };
    Solution().findSubstring(s,words);
    return 0;
}